Knapsack Algorithm
#Algorithm #Algorithm_Knapsack #Algorithm_DP
1. Knapsack?
배낭 문제 Wiki
=> 주어진 조건을 만족하는 집합 구성의 결과를 구할 때 사용할 수 있는 알고리즘
1-1. 왜 Knapsack 인가?
Knapsack이라고 붙인 의도를 이해하면 어떨 때 사용하는 알고리즘인지 이해하는게 더 수월해진다. Knapsack은 배낭이라는 뜻이다. 위의 정의를 이 배낭을 가지고 설명하면 다음과 같다.
"배낭이 찢어지지 않고 담아낼 수 있는 무게의 한계가 있다. 이 무게 내에서 가치가 다른 물건들을 선택해서 담을 수 있다. 이 때 물건들의 가치를 조건(최대 혹은 최소 혹은 다른 무언가)에 맞게 담는 물건들의 조합을 찾는다."
그러니까, 어떤 문제가 있는데 뭔가 조합을 하고 그 결과를 도출하라고 한다. 근데 이 문제들의 요소를 봤을 때, 배낭도 있고, 물건도 있고, 물건의 가치도 있다? 그럼 Knapsack으로 풀면 된다는 얘기가 된다.
2. Knapsack의 대표 종류
2-1. Fractional Knapsack
하나의 "물건"이 쪼개져서 담길 수 있다면 Fractional로 풀 수 있다.
Fractional Knapsack Problems
2-2. 0-1 Knapsack
물건을 쪼갤 수 없고, 배낭에 "넣거나" 혹은 "넣지 않는다"만을 선택할 수 있다면 0-1 Knapsack 문제이다. 0-1 Knapsack은 문제를 변형할 수 있는 요소가 굉장히 다양하다.
0-1 Knapsack Problems (All from Leetcode)
2742. Painting the Walls
279. Perfect Squares
322. Coin Change
416. Partition Equal Subset Sum
1049. Last Stone Weight II
3. Dynamic Programming을 사용하는 Knapsack
3-1. Dynamic Programming
Dynamic Programming은 문제를 작은 여러개의 문제로 나누어 부분해를 구해서 최종 결과를 도출하는 풀이 방식이다.
이름이 왜 다이나믹인지는 모르겠지만, DP에서 중요한 것은 문제를 작은 subproblem으로 나눈다는 것은 정말 당연한 것이고 여기에 memoization이 있어야 DP라고 불릴 수 있다. (DP를 하는 의미가 있기 때문이다.)
memoization은 subproblem의 결과를 저장해두는 것을 말한다. 이것을 저장해 두는 이유는 DP 한 문제를 풀게되면 같은 subproblem을 여러번 활용하게 되는데, 이 때마다 계산하지 않고 캐싱된 결과값을 사용해 중복적인 컴퓨팅 리소스를 사용하지 않게 해주기 때문이다.
DP는 수학적 귀납법을 생각하자.
DP를 풀려면 수학적 귀납법으로 어떻게 식을 만들어낼 수 있을까를 생각하면 쉽게 풀릴 수 있다. 이것이 알고리즘의 핵심이 된다.
DP는 Base Condition이 중요하다.
같은 문제를 풀더라도 방식이 조금이라도 바뀌면 (조회하는 인덱스의 순서 방향이나 memoization 자료구조의 형태) Base Condition이나 Limit Condition이 바뀐다. 이에 주의해서 알고리즘을 구성해야 한다.
3-2. Knapsack을 DP로 풀기 위해서는?
위에서 말한 DP를 풀기 위한 2가지를 생각하면 된다. 그에 앞서 이 문제가 Knapsack이라는 판단이 되면 문제의 요소 요소를 가방과 물건에 대입하여 기준을 잡아놓으면 큰 도움이 된다.
Knapsack에 대한 자세한 설명은 배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기, 호우동의 개발일지에 잘 정리되어 있다.
Knapsack을 이해하기 위해서 DP를 머릿속으로 계속 시뮬레이션해봤다. Knapsack은 문제 설명을 들을 때는 쉬워보이지만 다양한 베리에이션들을 마주하게되면 이게 이렇게 변한다고? 싶게 어렵게 느껴진다. (그러면서 개념의 와해까지 되버린다. subproblem이 과연 전체 problem에 독립적인 problem이 맞나 싶은 생각까지 가버린다..) 많이 풀어보고 계속 이해해보려고 노력하는 수밖에 없었다.
특히 잘 정리된 솔루션을 보는 것은 개인적으로 큰 도움이 되지 않았다. 솔루션을 최적화시키기 위해 사고의 많은 부분이 보이지 않고, 기술적으로 처리할 수 있는 부분은 처리가 되어 있었다. 우선 비효율적이고 느리더라도 나의 해답을 코드로 번역하는 작업을 하는것이 중요하다고 생각한다.